package com.tongtech.proxy.core.slices;

import java.util.ArrayList;
import java.util.List;

public class SignRSA {

    private static int targetX = 0;
    private static int targetY = 0;


    private static int row = 0;

    public int uniquePaths(int m, int n) {
        row = 0;

        this.targetX = m - 1;
        this.targetY = n - 1;

        int x = 0;
        int y = 0;

        move(new int[]{x, y}, null);

        return row;
    }

    public void move(int[] snapshot, int[] move) {
        if (move == null) {
            List<int[]> next = next(snapshot[0], snapshot[1]);
            if (next == null) {
                row = 1;
                return;
            }
            for (int[] ints : next) {
                move(snapshot, ints);
            }
        } else {

            if (move[0] == targetX && move[1] == targetY) {
                //到达目标终点
                row++;
                return;
            } else {
                List<int[]> next = next(move[0], move[1]);
                if (next != null) {
                    for (int[] ints : next) {
                        move(move, ints);
                    }
                }
            }
        }
    }

    public List<int[]> next(int x, int y) {
        List<int[]> result = new ArrayList<>();
        if (x == targetX && y == targetY) return null;
        if (x + 1 <= targetX) result.add(new int[]{x + 1, y});
        if (y + 1 <= targetY) result.add(new int[]{x, y + 1});
        return result;
    }
}
